Montículo suave

Montículo suave
En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos Montículo. Fue concebida por Bernard Chazelle en 2000. Al corromper (aumentar) cuidadosamente las claves de a lo sumo un cierto porcentaje fijo de valores en el montículo, logra obtener acceso en tiempo constante amortizado pra sus cuatro operaciones: ● create(S): Create un nuevo montículo suave ● insert(S, x): Inserta un elemento en un montículo suave ● meld(S, S' ): Combina el contenido de dos montículo suaves en uno. Ambos parámetros son destruidos en el proceso ● delete(S, x): Borra un elemento de un montículo suave ● findmin(S): Obtiene el elemento de clave mínima en el montículo suave Otros montículos como el montículo de Fibonacci logran este tipo de cota para algunas operaciones sin necesidad de corromper las claves, sin embargo, no logran acotar de forma constante la crítica operación delete. El porcentaje de valores que son modificados puede ser escogido libremente, pero mientras más bajo sea, más tiempo requieren las inserciones (O(log 1/e) para una tasa de e). Las corrupciones bajan efectivamente la entropía de información.

Enciclopedia Universal. 2012.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Montículo suave — Para otros usos de este término, véase Montículo (desambiguación). En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper… …   Wikipedia Español

  • Montículo (informática) — Para otros usos de este término, véase Montículo (desambiguación). Este artículo trata sobre la estructura de datos. Para el lugar de donde se asigna memoria dinámica, véase asignación dinámica de memoria. Este artículo o sección necesita… …   Wikipedia Español

  • Montículo (desambiguación) — El término montículo puede hacer referencia a: Montículo, como la pequeña colina, natural o artificial, que normalmente se encuentra aislada. Montículo, (heap en inglés) es una estructura de datos del tipo árbol con información perteneciente a un …   Wikipedia Español

  • Estructura de datos — En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Una estructura de datos… …   Wikipedia Español

  • Bernard Chazelle — Saltar a navegación, búsqueda Bernard Chazelle Bernard Chazelle (5 de noviembre de 1955) es un investigador francés en computación de la Universidad de Princeton. Es sobre todo conocido por su invención de la estructura de datos …   Wikipedia Español

  • Bernard Chazelle — (5 de noviembre de 1955) es un investigador francés en computación de la Universidad de Princeton. Es sobre todo conocido por su invención de la estructura de datos Montículo suave y el más asintoticamente eficiente algoritmo conocido para… …   Enciclopedia Universal

  • Nido de aves — Nido de copa profundo del carricero tordal (Acrocephalus arundinaceus). Un nido de ave es el lugar en el cual un ave pone e incuba sus huevos y cría sus polluelos. Mientras que el término popularmente se refiere a la estructura específica hecha… …   Wikipedia Español

  • Plaza Dealey — Distrito histórico de la Plaza Dealey Registro Nacional de Lugares Históricos (EE. UU.) Vista desde el sudoeste , con el edificio del Texas School Book Depository a la izquierda y el edificio Dal Tex a la derecha ,cerca de él …   Wikipedia Español

  • Anexo:Glosario de béisbol — Por ser un deporte de origen angloparlante y por su popularidad en una cantidad limitada de países de habla hispana, el béisbol tiene un glosario particular ampliamente influenciado por el mencionado origen y por las modificaciones particulares… …   Wikipedia Español

  • Glosario de béisbol — Anexo:Glosario de béisbol Saltar a navegación, búsqueda Por ser un deporte de origen angloparlante y por su popularidad en una cantidad limitada de países de habla hispana, el béisbol tiene un glosario particular ampliamente influenciado por el… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”